
class GetMaxMatrix {
  public int[] getMaxMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m+1][n+1];
    int max = Integer.MIN_VALUE;
    int[] result = new int[4];
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
        dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
      }
    }
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
        for(int t = 0; t < i; t++){
          for(int k = 0; k < j; k++){
            int sum = dp[i][j] - dp[i][k] - dp[t][j] + dp[t][k];
            if(sum > max){
              max = sum;
              result[0] = t;
              result[1] = k;
              result[2] = i - 1;
              result[3] = j - 1;
            }

          }
        }
      }
    }
    return result;
  }

  public static void main(String[] args) {
    GetMaxMatrix gmm = new GetMaxMatrix();
    int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int[] result = gmm.getMaxMatrix(matrix);
    System.out.println("[" + result[0] + ", " + result[1] + ", " + result[2] + ", " + result[3] + "]");
    
    // Test with example case
    int[][] matrix2 = {{-1, 0}, {0, -1}};
    int[] result2 = gmm.getMaxMatrix(matrix2);
    System.out.println("[" + result2[0] + ", " + result2[1] + ", " + result2[2] + ", " + result2[3] + "]");
  }
}

// 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

// 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

// 注意：本题相对书上原题稍作改动

// 示例：

// 输入：
// [
//    [-1,0],
//    [0,-1]
// ]
// 输出：[0,1,0,1]
// 解释：输入中标粗的元素即为输出所表示的矩阵
 

// 说明：

// 1 <= matrix.length, matrix[0].length <= 200